import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BinaryTree {

        static class TreeNode{
            TreeNode left;
            TreeNode right;
            char val;
            TreeNode(char value){
                this.val= value;
            }
        }

        public TreeNode createTree(){
            TreeNode A = new TreeNode('A');
            TreeNode B = new TreeNode('B');
            TreeNode C = new TreeNode('C');
            TreeNode D = new TreeNode('D');
            TreeNode E = new TreeNode('E');
            TreeNode F = new TreeNode('F');
            TreeNode G = new TreeNode('G');
            TreeNode H = new TreeNode('H');

            A.left  = B;
            A.right = C;
            B.left  = D;
            B.right = E;
            C.left  = F;
            C.right = G;
            E.right = H;
            return A;
        }
        //前序遍历
        void preOrder(TreeNode root){
            if(root==null)return;
            System.out.println(root.val+" ");
            preOrder(root.left);
            preOrder(root.right);

        }
        //中序遍历
        void inOrder(TreeNode root){
            if(root==null)return;
            inOrder(root.left);
            System.out.println(root.val+" ");
            inOrder(root.right);
        }
        //后序遍历
        void postOrder(TreeNode root){
            if(root==null)return;
            inOrder(root.left);
            inOrder(root.right);
            System.out.println(root.val+" ");
        }


    public List<List<Character>>levelOrder(TreeNode root){
            List<List<Character>>ret = new ArrayList<>();//顺序表ret 里＋外
             if(root == null) return ret;
        Queue<TreeNode> queue = new LinkedList<>();//用链表写队列 用来offer和poll节点
        queue.offer(root);

        while(!queue.isEmpty()){//算队列不为空时候，的size
            int size = queue.size();
            List<Character>list =new ArrayList<>();//顺序表list 里
             while(size != 0){
                 TreeNode cur = queue.poll();//cur接收队里poll出来的
                 list.add(cur.val);//顺序表list 里 接收队里poll出来的
                 size--;
                 if(cur.left!=null){
                     queue.offer(cur.left); //添加到队里
                 }
                 if(cur.right !=null){
                     queue.offer(cur.right);
                 }
             }
             ret.add(list);
        }
        return ret;
    }

}
